<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /* 
      思路：拆分成两个相等和的子集，等同于背包容量为总和的一半，它的最大价值是否等同于一半
      */
      var canPartition = function (nums) {
        nums.sort((a, b) => a - b);
        let sum = nums.reduce((pre, item) => (pre += item));
        if (sum % 2 != 0) return false;
        let bagSize = sum / 2;
        let dp = new Array(bagSize + 1).fill(0);
        //外层物品，内层背包，从大到小遍历
        for (let i = 0; i < nums.length; i++) {
          for (let j = bagSize; j >= nums[i]; j--) {
            dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
          }
        }
        //dp[bagSize]可以得到装满背包的最大价值，判断是否是和的一半即可，且每个元素只能用一次
        if (dp[bagSize] == bagSize) return true;
        return false;
      };
    </script>
  </body>
</html>
